#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2, mod = 10000;
int n;
void mulfa(int f[], int a[], int b[][N])
{
    int tmp[N] = { 0 };
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            tmp[i] = (tmp[i] + a[j] * b[j][i]) % mod;
        }
    }
    memcpy(f, tmp, sizeof tmp);
}
void mulff(int f[][N], int a[][N], int b[][N])
{
    int tmp[N][N] = { 0 };
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    memcpy(f, tmp, sizeof tmp);
}
int main()
{
    while ((cin >> n, n >= 0))
    {
        int f[N] = { 0,1 };
        int a[N][N] = { {0,1},{1,1} };
        int k = n;
        while (k)
        {
            if (k & 1) mulfa(f, f, a);
            mulff(a, a, a);
            k >>= 1;
        }
        cout << f[0] << endl;
    }
    return 0;
}